#include<iostream>
#include<assert.h>
using namespace std;
template<class T>
struct ListNode
{
  ListNode<T>* next;
  T val;
  ListNode(const T& v)
    :val(v),next(nullptr)
  {}
  ListNode() //提供一个默认构造函数,防止报错
    :next(nullptr)
  {}
  ~ListNode()
  {
    next = nullptr;
  }
};
//注意:链表节点的类型是ListNode<T>
//基本思路:链表的头作为栈底,尾作为栈顶
//所以插入：尾插 删除:尾删
template<class T>
class Stack
{
public:
 Stack()
   :tail(nullptr),_size(0)
 {}
 ~Stack()
 {}
 //插入
 void push(const T& val = T()) //没有给值,则插入默认值
 {
   ListNode<T>* newnode = new ListNode<T>(val);
   newnode->next = tail; //哪怕当前链表为空也可以
   tail = newnode;
   _size++;
 }
 //弹出栈顶元素
 void pop()
 {
  assert(!empty()); 
  ListNode<T>* del = tail;
  tail = tail->next;
  delete del;
  _size--;
 }
 //判断是否为空
 bool empty() const 
 {
    return _size == 0; //return tail == nullptr;
 }
 //获取栈中元素个数
 size_t size() const 
 {
    return _size;
 }
 
 //得到栈顶元素
 T& top() const 
 {
   assert(!empty());//assert里面的判断为假就报错
   return tail->val;
 }
private:
  ListNode<T>* tail;//标记栈顶节点
  size_t _size= 0 ;//元素个数
};
